// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-23 19:52
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain;

import java.util.*;

@SuppressWarnings("ALL")
public class NetWorkBecomeIdle {
    /**
     * 网络空闲时刻 -> 1. HashMap邻接表建图 + BFS寻找当前最短路径
     */
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        /*-----邻接表，key是图节点，list是和当前节点联通的节点链表-----*/
        Map<Integer, List<Integer>> neiborLinkList = new HashMap<Integer, List<Integer>>();
        /*-----邻接表初始化-----*/
        for (int[] edge : edges) {
            List<Integer> UnicomNodeList_a = neiborLinkList.getOrDefault(edge[0], new ArrayList<Integer>());
            List<Integer> UnicomNodeList_b = neiborLinkList.getOrDefault(edge[1], new ArrayList<Integer>());
            UnicomNodeList_a.add(edge[1]);
            UnicomNodeList_b.add(edge[0]);
            neiborLinkList.put(edge[0], UnicomNodeList_a);
            neiborLinkList.put(edge[1], UnicomNodeList_b);
        }
        /*-----图的BFS遍历-----*/
        // 辅助队列的创建
        Deque<Integer> deque = new ArrayDeque<Integer>();
        deque.add(0);
        // 定义当前路径长度变量
        int len = 1, ans = 0, layer = 1, nLayer = 0;
        // 用于储存服务器到主服务器的距离
        int[] path = new int[patience.length];
        Arrays.fill(path, -1);
        path[0] = 0;
        while (!deque.isEmpty()) {
            Integer node = deque.poll();
            layer--;

            // 使用邻接链表访问当前层的节点
            List<Integer> neiborNode = neiborLinkList.get(node);
            for (Integer integer : neiborNode) {
                if (path[integer] == -1) {
                    path[integer] = len;
                    deque.add(integer);
                    nLayer++;
                }
            }
            if (layer == 0) {
                layer = nLayer;
                len++;
                nLayer = 0;
            }
        }
        /*-----根据计算所得的路径计算网络的最小空闲时间-----*/
        for (int i = 1; i < path.length; i++) {
            int t = 0, d = 2 * path[i];
            if (d < patience[i]) {
                t = d;
            } else {
                t = (d - 1) / patience[i] * patience[i] + d;
            }
            ans = Math.max(ans, t);
        }
        /*---刚开始的时候需要一秒进行初始化---*/
        return ans + 1;
    }
}

@SuppressWarnings("ALL")
class NetWorkBecomeIdleByCFS {
    int N = 100010, M = 2 * N;
    /**
     * 链式前向星的创建需要三个数组
     * head[]: 存储和当前节点联通的最大索引序号节点序号
     * edge[]: 存储当前节点指向的下一条边
     * to[]: 当前边指向的节点
     */
    int idx = 0, INF = 0x3f3f3f3f;
    int[] head = new int[N], edge = new int[M], to = new int[M];


    /*-----链式前向星标构图方法-----*/
    void add(int a, int b) {
        edge[idx] = head[a];
        to[idx] = b;
        // 当前节点边信息索引
        head[a] = idx++;
    }


    /**
     * 使用链式前向星方法建图
     */
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Arrays.fill(head, -1);
        Arrays.fill(edge, 0);
        Arrays.fill(to, -1);
        for (int[] ints : edges) {
            // 因为是无向图，所以两个节点都需要记录当前边的信息
            add(ints[0], ints[1]);
            add(ints[1], ints[0]);
        }
        /*-----使用BSF遍历构建的图，获取每一个节点的最短路径-----*/
        // BSF遍历所需要的队列
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(0);
        int[] dist = new int[patience.length];
        // 主服务器到主服务器的距离为0
        Arrays.fill(dist, INF);
        dist[0] = 0;
        while (!deque.isEmpty()) {
            Integer node = deque.poll();
            for (int i = head[node]; i != -1; i = edge[i]) {
                int j = to[i];
                if (dist[j] != INF) {
                    continue;
                }
                dist[j] = dist[node] + 1;
                deque.offer(j);
            }
        }

        /*-----判断网络最短空闲时间-----*/
        int ans = 0;
        for (int i = 1; i < patience.length; i++) {
            int d = dist[i] * 2, t = patience[i];
            int cur = d <= t ? d : (d - 1) / t * t + d;
            if (cur > ans) {
                ans = cur;
            }
        }
        return ans + 1;
    }
}
